package pro.softzhang.algo.lc0;

import pro.softzhang.algo.common.TreeNode;
import pro.softzhang.algo.flag.knowledge.KBinaryTree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 中序遍历
 */
@KBinaryTree
public class LC94_BinaryTreeInorderTraversal {
    public static void main(String[] args) {

    }

    static
    class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> l = new ArrayList<>();
            if (root == null) return l;
            doInorderTraversal(root, l);
            return l;
        }

        private void doInorderTraversal(TreeNode root, List<Integer> l) {
            if (root == null) {
                return;
            }
            doInorderTraversal(root.left, l);
            l.add(root.val);
            doInorderTraversal(root.right, l);
        }
    }

    /**
     * 中序遍历迭代实现
     */
    static
    class Solution1 {
        public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> l = new ArrayList<>();
            Stack<TreeNode> s = new Stack<>();
            TreeNode p = root;
            while (p != null || !s.isEmpty()) {
                if (p != null) {
                    s.push(p);
                    p = p.left;
                } else {
                    p = s.pop();
                    l.add(p.val);
                    p = p.right;
                }
            }
            return l;
        }
    }
}
